package com.cjm.algorithm.str;

public class Ti24042228 {
    public static void main(String[] args) {
        Ti24042228 ti24042228 = new Ti24042228();
        System.err.println(ti24042228.strStr("mississippi", "issipi"));
        int[] aaabbabs = ti24042228.getNextArray("adcadde");
        int[] aaabbabaz = ti24042228.getNextArray3("adcadde");
        System.err.println("OK");
    }

    public int strStra(String haystack, String needle) {
        int length1 = needle.length();
        if (length1 == 0) {
            return 0;
        }
        int[] next = getNextArray(needle);
        int length = haystack.length();
        for (int i = 0, j = 0; i < length; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == length1) {
                return i - length1 + 1;
            }
        }
        return -1;
    }

    private int[] getNextArray(String needle) {
        int[] next = new int[needle.length()];
        int i = 0, j = 1;
        next[0] = 0;
        while (j < needle.length()) {
            if (needle.charAt(i) == needle.charAt(j)) {
                next[j] = i + 1;
                i++;
                j++;
                continue;
            }
            if (i == 0) {
                next[j] = 0;
                j++;
                continue;
            }
            i = next[i - 1];
        }
        return next;
    }

    private int[] getNextArray3(String needle) {
        int[] pi = new int[needle.length()];
        for (int i = 1, j = 0; i < needle.length(); i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        return pi;
    }

    public int strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()) {
            return -1;
        }
        for (int i = 0; i < haystack.length(); i++) {
            if ("OK".equals(extracted(haystack, needle, i))) {
                return i;
            }
        }
        return -1;
    }

    private static String extracted(String haystack, String needle, int i) {
        for (int j = 0; j < needle.length(); j++) {
            if (i >= haystack.length()) {
                return "";
            }
            if (haystack.charAt(i) != needle.charAt(j)) {
                return "";
            }
            i++;
        }
        return "OK";
    }
}
